/**
 * 解读：
 * 
 * 字符串匹配，获取首次匹配到的下标
 */

/**
 * 解法1：string api
 * 
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if(!haystack || haystack.length==0){
        return -1;
    }
    if(!needle || needle.length==0){
        return -1;
    }
    if(haystack === needle){
        return 0;
    }
    if(haystack.length <= needle.length){
        return -1;
    }


    return haystack.indexOf(needle);
};

/**
 * 解法2：使用数组，string转换为数组，从头遍历
 * 
 * @param {*} haystack 
 * @param {*} needle 
 * @returns int
 */
var strStr = function(haystack, needle) {
    if(!haystack || haystack.length==0){
        return -1;
    }
    if(!needle || needle.length==0){
        return -1;
    }
      if(haystack === needle){
        return 0;
    }
    if(haystack.length <= needle.length){
        return -1;
    }

    //字符串解构为数组
    let haystackArray = [...haystack];
    let needleArray = [...needle];


    for(let index = 0; index <= haystackArray.length-needleArray.length; index++){
        for(let j= 0;j<needleArray.length; j++){
            if(haystackArray[j+index]!==needleArray[j]){
                //移动index
                break;
            }else if(j === needleArray.length-1){
                //到最后一个元素，仍然相等，那么认为当前的index 是匹配到的位置
                return index;
            } 
        }
    }

    return -1;
};


/**
 * 解法3：使用正则
 * 
 * @param {*} haystack 
 * @param {*} needle 
 * @returns int
 */
var strStr = function(haystack, needle) {
    if(!haystack || haystack.length==0){
        return -1;
    }
    if(!needle || needle.length==0){
        return -1;
    }
      if(haystack === needle){
        return 0;
    }
    if(haystack.length <= needle.length){
        return -1;
    }

    return haystack.search(needle);
};

/**
 * 解法4：KMP 减少重复的算法原则，进一步优化解法2
 * 
 * 怎么优化？答: acabd，  匹配ab。 先匹配首字母a，再匹配c，不符合时不从下个index开始，而是从下一个a的位置开始匹配，也就是从第三个位置的a匹配
 * 
 * 
 */
